package LeetCode;

public class LC502 {
    // 回溯法【超时】
    private int ans = 0;

    public static void main(String[] args) {
        LC502 lc502 = new LC502();
        System.out.println(lc502.findMaximizedCapital(1, 2, new int[]{1, 2, 3}, new int[]{1, 1, 2}));
    }

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        traceBack(w, profits, capital, k, 0);
        return ans;
    }

    private void traceBack(int w, int[] profits, int[] capital, int k, int index) {
        ans = Math.max(ans,w);
        if (k == 0) return;
        for (int i = index; i < profits.length; i++) {
            if(w>= capital[i]){
                traceBack(w+profits[i],profits,capital,k-1,i+1);
            }
        }
    }
}
